package two.stack_queue;

import java.util.Arrays;
import java.util.Stack;

/**
 *  柱状图中最大的矩形 （单调栈模板）
 *  时间复杂度：O(n) 每个柱子入栈、出栈各一次，2n=O(n)
 *  思路：单调栈（不止和两端的柱子有关，也和中间的柱子有关）
 *  维护一个单调递增的序列
 */
public class LargestRectangleArea {

    //方法一：单调栈存矩形rect的宽度和高度
    //注意点：宽度的累加
    public int largestRectangleArea(int[] heights) {
        heights = Arrays.copyOf(heights, heights.length + 1); //在最后面补一个“0”，帮助我们在最后把单调栈清空
        Stack<Rect> s = new Stack<>(); //单调栈
        int answer = 0; //结果
        // 第一步：for 每个元素
        for(int h : heights){
            int accumulated_width = 0; //每一块的累计宽度
            // 第二步：while (栈顶不满足高度单调性) 累加宽度，出栈
            while(!s.empty() && s.peek().height >= h){
                accumulated_width += s.peek().width;
                answer = Math.max(answer, s.peek().height * accumulated_width);
                s.pop();
            }
            // 第三步：新元素入栈
            Rect rect = new Rect();
            rect.height = h;
            rect.width = accumulated_width + 1;
            s.push(rect);
        }
        return answer;
    }
    private class Rect{
        int height;
        int width;
    }

    //方法二：单调栈存heights的下标（宽度由计算的来）
    //注意点：要先出栈，在求left（因为累加宽度）
    public int largestRectangleArea2(int[] heights) {
        Stack<Integer> stack = new Stack<>(); //单调栈
        int area = 0; //结果
        // 第一步：for 每个元素
        for(int i = 0; i <= heights.length; i++){
            int cur = i == heights.length ? -1 : heights[i]; //帮助我们在最后把单调栈清空
            // 第二步：while 
            while(!stack.isEmpty() && cur <= heights[stack.peek()]){
                int h = heights[stack.pop()]; //注意点：要先出栈，在求left（因为累加宽度）
                int left = stack.isEmpty() ? 0 : (stack.peek() + 1);
                area = Math.max(area, (i - left) * h);
            }
            // 第三步：新元素入栈
            stack.push(i);
        }
        return area;
    }
}
